package com.liang.bishi.xy;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 9.26 信也科技
 * 第一题：实现一个函数 findFirstNode(TreeNode root TreeNode p,TreeNode q)，找到二叉树中两个节点的最近公共祖先，
 * 每个节点都有一个颜色属性（红色或蓝色)在确定最近公共祖先时,如果遇到一个节点,它的颜色与p和q的颜色任意一个不同,那么这个节点不能被视为公共祖先。
 * 二叉树为满二叉树,二叉树中每个节点的value值均不同。
 * <p>
 * 1-红,2-蓝,3-红,4-红,5-红,6-蓝,7-红
 * 4
 * 6
 */
public class Problem1 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String treeNodes = in.nextLine();
        int pValue = in.nextInt();
        int qValue = in.nextInt();
        TreeNode root = buildTree(treeNodes);
        TreeNode p = search(root, pValue);
        TreeNode q = search(root, qValue);
        TreeNode node = findFirstNode(root, p, q);
        if (node != null) {
            System.out.println(node.value + "-" + node.color);
        } else {
            System.out.println("未查询到公共祖先节点");
        }
    }

    /**
     * 找 p q 节点的最近公共祖先
     */
    public static TreeNode findFirstNode(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        // 找到了 p 或 q 并返回
        if (root == p || root == q) {
            return root;
        }
        // 后序遍历，递归查找左、右子树中 p 和 q 的最近公共祖先
        TreeNode left = findFirstNode(root.left, p, q);
        TreeNode right = findFirstNode(root.right, p, q);
        // 如果左右子树都找到 p 或 q，说明当前节点是最近公共祖先
        if (left != null && right != null) {
            return root;
        }
        // 检查当前节点的颜色是否与 p 和 q 的颜色一致
        if (root.color.equals(p.color) && root.color.equals(q.color)) {
            return root; // 当前节点是公共祖先
        }
        // 没找到
        return null;
    }

    /**
     * 字符串转为满二叉树
     */
    public static TreeNode buildTree(String str) {
        String[] nodes = str.split(",");
        List<TreeNode> levelNodes = new ArrayList<>();
        for (String node : nodes) {
            String[] parts = node.split("-");
            int value = Integer.parseInt(parts[0]);
            String color = parts[1];
            levelNodes.add(new TreeNode(value, color));
        }
        return buildTreeHelper(levelNodes, 0);
    }

    private static TreeNode buildTreeHelper(List<TreeNode> nodes, int index) {
        if (index >= nodes.size()) {
            return null;
        }
        TreeNode node = nodes.get(index);
        node.left = buildTreeHelper(nodes, 2 * index + 1);
        node.right = buildTreeHelper(nodes, 2 * index + 2);
        return node;
    }

    public static TreeNode search(TreeNode root, int value) {
        if (root == null) {
            return null;
        }
        if (root.value == value) {
            return root;
        }
        TreeNode leftResult = search(root.left, value);
        if (leftResult != null) {
            return leftResult;
        }
        return search(root.right, value);
    }

}

class TreeNode {
    int value;
    String color; //节点的颜色，可以是红色或蓝色
    TreeNode left;
    TreeNode right;

    TreeNode(int value, String color) {
        this.value = value;
        this.color = color;
    }
}





